home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / Programming / Source / 2DLab / farthest.m < prev    next >
Encoding:
Text File  |  1992-05-19  |  8.2 KB  |  269 lines
  1.  
  2. #include <stdlib.h>
  3. #ifdef MYDIR
  4. #else
  5. #include "TwoDView.h"
  6. #include "TwoDTSP.h"
  7. #include <appkit/graphics.h>
  8. #endif
  9. #include <math.h>
  10. #include <limits.h>
  11. #include <stdio.h>
  12. #include "tspheaders.h"
  13. #include "prototypes.h"
  14. /************************************************************************/
  15. /* This function implements the Farthest Insertion Algorithm for the
  16.    Travelling Salesperson Algorithm.  It provides an approximate optimal
  17.    value rather than the optimal value. 
  18.  
  19.    Reference: Lawler, Lenstra, et. al., The Traveling Salesman [sic] Problem,
  20.              1985, Wiley and Sons, p 226.
  21.  
  22. */
  23. /************************************************************************/
  24. /* Parameters:   TwoDView *self: Ye Old Drawing Object
  25.  
  26.                     float *Data: Pointer to the list of points.
  27.                                  Used to draw intermediate graph.
  28.  
  29.                 float *Distance: Pointer to area that contains the
  30.                                  Distances Between Each Pair of Cities
  31.  
  32.                       int *Tour: Pointer to area that will contain the
  33.                                  indices of the n arcs that are selected 
  34.                                  to be a part of the tour
  35.  
  36.              int NumberOfCities: Number of cities in the problem
  37. */
  38. /************************************************************************/
  39. /************************************************************************/
  40. #ifdef MYDIR
  41. float FarthestInsertion(float *Distance,int *Tour,int NumberOfCities) {
  42. #else
  43. float FarthestInsertion(TwoDView *self,float *data,float *Distance,int *Tour,
  44.                         int NumberOfCities) {
  45. #endif
  46. int i,j,k,m,x,y,I,J,
  47.     From,To,CurrentCity,SubTourEnd,TourIndex,NewCity,
  48.     City1,City2,LeavingArc;
  49. int *OnTour, *TourCities;
  50. float NewDistance,MinDistance,ThisDistance,OptimalValue;
  51. char msg[256];
  52.  
  53. /* allocate space for OnTour and TourCities */
  54. OnTour = (int *)malloc(NumberOfCities*sizeof(int));
  55. TourCities = (int *)malloc(NumberOfCities*sizeof(int));
  56. if (OnTour == (int *) 0)
  57.   printf("Malloc for OnTour failed. \n");
  58. if (TourCities == (int *) 0)
  59.   printf("Malloc for TourCities failed. \n");
  60. for (i=0;i<NumberOfCities;i++) {
  61.    OnTour[i] = 0;
  62.  }
  63. for (i=0;i<NumberOfCities;i++) {
  64.    TourCities[i] = 0;
  65.  }
  66.  
  67. #ifdef DEBUGMYDIR
  68.  for (i=0;i<(NumberOfCities-1)*NumberOfCities/2;i++) {
  69.    printf("Distance[%d] = %f; \n",i,Distance[i]);
  70.  }
  71.  #endif
  72.  
  73.  /* find the two cities with the maximum distance */
  74.  /* these two cities make up the initial subtour  */
  75.  NewDistance = FarthestCities(Distance,&From,&To,NumberOfCities);
  76.  
  77.  /* if NewDistance doesn't change, there is a problem ... */
  78.  if (NewDistance == 0) {
  79.    printf("Error no initial subtour found. \n");
  80.  }
  81.  #ifdef DEBUGMYDIR
  82.  else {
  83.    printf("initial subtour \n");
  84.    printf("from %d to %d distance %f \n",From,To,NewDistance);
  85.  }
  86.  #endif
  87.  
  88.  /* given a subtour of m cities, add city k with minimum insertion cost */
  89.  /* cost of inserting city k between cities i and j =
  90.               Distance(i,k) + Distance(k,j) - Distance(i,j) */
  91.  
  92.  /* OnTour is a list of cities on the tour already. */
  93.  Tour[0] = Tour[3] = From;
  94.  Tour[1] = Tour[2] = To;
  95.  OnTour[From] = OnTour[To] = 1;
  96.  TourCities[0] = From;
  97.  TourCities[1] = To;
  98.  OptimalValue = 2*NewDistance;
  99.  
  100.  SubTourEnd = 1;
  101.  TourIndex = -1;
  102.  NewCity = NumberOfCities;
  103.  NewDistance = 0; 
  104.  
  105.  /* keep adding cities until you include all NumberOfCities of them */
  106.  while (SubTourEnd < NumberOfCities-1) {
  107.  #ifdef DEBUGMYDIR
  108.    printf("Start of Iteration with %d cities in tour \n",SubTourEnd+1);
  109.  #endif
  110.    /* at the end of this while loop, there will be a new city to insert */
  111.    while (TourIndex < SubTourEnd) {
  112.      /* look at the next city already on the tour */
  113.      TourIndex+=1;
  114.      CurrentCity = TourCities[TourIndex];
  115.  #ifdef DEBUGMYDIR
  116.        printf("Looking at city %d \n",CurrentCity);   
  117.  #endif
  118.      /* look at all arcs starting at CurrentCity */
  119.      I = ArcIndex(CurrentCity,NumberOfCities);
  120.      J = ArcIndex((CurrentCity+1),NumberOfCities);
  121.      for (i=I;i<J;i++) {
  122.        /* j = terminating end of this arc */
  123.        j = i-I+CurrentCity+1;
  124.        /* if the city at the other end isn't already on the tour ...*/
  125.        if (!OnTour[j]) {
  126.          /* Is the arc a new candidate for insertion? */
  127.      k = kfrom(CurrentCity,j,NumberOfCities);
  128.      if (Distance[k] > NewDistance) {
  129.  #ifdef DEBUGMYDIR
  130.        printf("Changing cities from %d to %d \n",NewCity,j);   
  131.        printf("Looking at city %d \n",CurrentCity);   
  132.  #endif
  133.        NewDistance = Distance[k];
  134.        NewCity = j;
  135.      } 
  136.        } 
  137.      }
  138.  
  139.      /* look at all arcs ending at CurrentCity */
  140.      for (m=0;m<CurrentCity;m++) {
  141.        /* if the starting city isn't already on the tour ...*/
  142.        if (!OnTour[m]) {
  143.          /* Is this arc a new candidate for insertion? */
  144.          k = kfrom(m,CurrentCity,NumberOfCities);
  145.          if (Distance[k] > NewDistance) {
  146.  #ifdef DEBUGMYDIR
  147.            printf("Changing cities from %d to %d \n",NewCity,m);   
  148.  #endif
  149.            NewDistance = Distance[k];
  150.        NewCity = m;
  151.      } 
  152.        }
  153.      }
  154.    }
  155.  
  156.    if (NewCity >= NumberOfCities) {
  157.      printf("Error: new city has not been found for tour. \n");
  158.      CurrentCity = SubTourEnd = NumberOfCities;
  159.      OptimalValue = -1;
  160.    }
  161.    else {
  162.      /* find two cities on the tour, City1 and City2 such that the 
  163.         distance from City1 to the NewCity plus the distance from 
  164.         the NewCity to City2 - the distance from City1 to City2 is
  165.         minimized. */
  166.      k = 0;
  167.      MinDistance = INT_MAX;
  168.  #ifdef DEBUGMYDIR
  169.      printf("NewCity is %d SubTourEnd %d \n",NewCity,SubTourEnd);
  170.  #endif
  171.      while (k <= 2*SubTourEnd) {
  172.        City1 = Tour[k];
  173.        City2 = Tour[k+1];
  174.        ThisDistance = Distance[kfrom(City1,NewCity,NumberOfCities)] +
  175.                       Distance[kfrom(City2,NewCity,NumberOfCities)] -
  176.                       Distance[kfrom(City1,City2,NumberOfCities)];
  177.  #ifdef DEBUGMYDIR
  178.        printf("This %f Min %f City1 %d City2 %d \n",ThisDistance, MinDistance,City1,City2);
  179.  #endif
  180.        if (ThisDistance < 0) {
  181.          printf("Error: ThisDistance = %f for City1 %f City2 %f NewCity %f \n",
  182.                  City1,City2,NewCity);
  183.        }
  184.  
  185.        if (ThisDistance < MinDistance) {
  186.          MinDistance = ThisDistance;
  187.          LeavingArc = k;
  188.        }
  189.        k+=2;
  190.      }
  191.  
  192.      if (MinDistance == INT_MAX) {
  193.        printf("Error: wasn't able to find a spot for %d \n",NewCity);
  194.      }
  195.      
  196.      /* arc in Tour starting at LeavingArc is replaced by arcs
  197.         between Tour[LeavingArc] and NewCity and arc between 
  198.         NewCity and Tour[LeavingArc+1]. */
  199.  
  200.        /* add the new arc going from NewCity to Tour[LeavingArc+1] */
  201.  #ifdef DEBUGMYDIR
  202.      printf("adding arc from %d to %d \n",NewCity,Tour[LeavingArc+1]);
  203.  #else
  204.      sprintf(msg,"add arc %d to %d \n",NewCity,Tour[LeavingArc+1]);
  205.      STATUS(msg);
  206.  #endif
  207.        SubTourEnd+=1;
  208.        Tour[2*SubTourEnd] = NewCity;
  209.        Tour[2*SubTourEnd+1] = Tour[LeavingArc+1];
  210.        OnTour[NewCity] = 1;
  211.        TourCities[SubTourEnd] = NewCity;
  212.  
  213.  #ifdef DEBUGMYDIR
  214.        printf("replacing arc from %d to %d with %d to %d \n",
  215.                Tour[LeavingArc],Tour[LeavingArc+1],Tour[LeavingArc],NewCity);
  216.  #else
  217.        sprintf(msg,"replacing arc from %d to %d with %d to %d \n",
  218.                Tour[LeavingArc],Tour[LeavingArc+1],Tour[LeavingArc],NewCity);
  219.        STATUS(msg);
  220.  #endif
  221.        Tour[LeavingArc+1] = NewCity;
  222.  
  223.        /* update the Optimal Value */  
  224.        OptimalValue+=MinDistance;
  225.  
  226.  #ifdef DEBUGMYDIR
  227.        printf("addding %f to Opval to get %f \n",MinDistance,OptimalValue);
  228.  #else
  229.        sprintf(msg,"addding %f to Opval to get %f \n",MinDistance,OptimalValue);
  230.        STATUS(msg);
  231.  #endif
  232.      }
  233.  
  234.      /* get ready to start at the top of the list again */
  235.      TourIndex = -1;
  236.      NewDistance = 0; 
  237.      NewCity = NumberOfCities; 
  238.  
  239.  #ifdef DEBUGMYDIR
  240.      /* print out current subtour */ 
  241.      for (i=0;i<2*(SubTourEnd+1);i++) {
  242.        printf("i tour %d %d \n",i,Tour[i]);
  243.      }
  244.  #endif
  245.  #ifdef MYDIR
  246.  #else
  247.      /* draw the intermediate tour */
  248.      PSnewinstance();
  249.     for(i=0;i<2*(SubTourEnd+1);i+=2) { 
  250.      x = Tour[i];
  251.      y = Tour[i+1];
  252.      [self drawEdge:X(x):Y(x):X(y):Y(y)];
  253.  
  254.     }
  255.    NXPing();
  256.    [self->optimalValueField setFloatValue: OptimalValue at: 0];
  257.    usleep(self->drawTime);
  258. #endif
  259.     
  260. }
  261.  
  262. /* clean up */
  263. free(OnTour);
  264.  
  265. /* return the optimal value */
  266. return(OptimalValue);
  267. }
  268.         
  269.